Міністерство освіти та науки України Національний університет «Львівська політехніка» кафедра прикладної математики КУРСОВА РОБОТА з курсу дискретної математики на тему: «Граматики передування. Алгоритм типу «перенос-згортка». Граматики простого, розширеного та слабкого передування» Анотація У даній курсовій роботі розглянуто один з класів КВ – граматик, а саме – граматики передування. Дано загальну характеристику цього класу граматик, нижче розглянуто основні типи граматик передування, а саме – граматики простого, розширеного та слабкого передування. Також розглянуто алгоритм типу «перенос-згортка», що дає можливість побудувати розпізнавач стрічок та встановити їх належність введеній граматиці. Крім того розглянуто відношення передувань Вірта-Вебера – що дають можливість зберігати інформацію про зв’язки між символами в граматиці, також показана різниця між граматиками простого, розширеного та слабкого передування, різниця в реалізації алгоритму «перенос-згортка» для кожного з цих типів. На сам кінець – наведено реалізацію алгоритму «перенос-згортка» - код програми, що перевіряє належність вхідної стрічки до введеної граматики. Зміст Титульна сторінка 1 Анотація 2 Зміст 3 Вступ 4 Граматики. Основні характеристики. КВ – граматики 5 Граматики передування 6 Алгоритм «перенос-згортка» 8 Граматики простого передування 11 Алгоритм "перенос - згортка " для граматик простого передування 15 Граматики розширеного передування 17 Побудова відношень (m,n)- передування 19 Граматики слабкого передування 21 Алгоритм "перенос-згортка" для граматик слабкого передування. 24 Алгоритм переходу від оборотного слабкого передування до простого передування 26 Висновок 28 Додаток(текст програми) 29 Список використаної літератури 30 Вступ У спілкуванні людини і машини (комп'ютера) існують природні труднощі. Машини оперують бітами і регістрами, а люди користуються природними мовами або користуються певною системою позначень (наприклад, мова математичних формул). Щоб спілкування з машиною стало можливим, людина одержує інструкцію для користувача, у якій пояснюються всі допустимі мовні конструкції та значення, а для комп'ютера розробляється програмне забезпечення, за допомогою якого він може сприймати послідовності бітів для позначення команд або програми, написані на деякій штучній мові, і перекладати їх у внутрішні бітові структури. Програму для обчислювальної машини, що дозволяє їй «розуміти» директиви і речення вхідної мови, яку використовує програміст, будемо називати «мовним процесором». Розрізняють два типи мовних процесорів: інтерпретатори і транслятори. Різниця між ними полягає в тому, що інтерпретатор аналізуючи об’єкт програми – одночасно виконує відповідні дії, а транслятор – формує так званий об’єктний код, який пізніше виконується після остаточного формування. Першим етапом трансляції вхідної програми є лексичний аналіз(сканування). Сканер проглядає літери вхідної програми зліва направо і будує символи (лексеми, слова, атоми) програми − цілі числа, ідентифікатори, службові слова, двосимвольні розділювачі. Символи передаються після цього на обробку фактичному аналізатору (синтаксичному). Перед синтаксичним аналізатором стоять два основні завдання: перевірити правильність конструкцій програми, яка представляється у вигляді вже виділених слів вхідної мови, і перетворити її у вигляд, зручний для подальшої семантичної обробки і генерації коди. Іншими словами, на етапі синтаксичного аналізу потрібно встановити, чи має ланцюжок лексем структуру, задану синтаксисом мови, а також зафіксувати цю структуру. Отже, знову треба вирішувати задачу розбору: даний ланцюжок лексем, і треба визначити, чи виводиться вона в граматиці, що визначає синтаксис мови. Проте структура синтаксису мови, представленої у вигляді таких конструкцій як: вирази, описи, оператори і тому подібне, складніша, ніж структура лексем. Для опису синтаксису мов програмування використовують такі структури як граматики, а конкретніше один з класів – граматики передування, для яких і...